package com.linyaonan.leetcode.sword_to_offer._49;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
 *
 *  
 *
 * 示例:
 *
 * 输入: n = 10
 * 输出: 12
 * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 * 说明:  
 *
 * 1 是丑数。
 * n 不超过1690。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/chou-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public int nthUglyNumber(int n) {
        if (n == 1) {
            return 1;
        }

        int uCount = 1;
        int thisU = 1;

        int start = 2;
        while (uCount != n) {
            if (isU(start)) {
                thisU = start;
                uCount++;
            }
            start++;
        }

        return thisU;
    }

    public int nthUglyNumber2(int n) {
        if (n == 1) {
            return 1;
        }

        long current = 1;
        Set<Long> vis = new HashSet<>();
        Queue<Long> q = new PriorityQueue<>();
        q.add(current);
        int cnt = 0;
        while(!q.isEmpty()){
            current = q.poll();
            if(!vis.contains(current)){
                q.add(current*2);
                q.add(current*3);
                q.add(current*5);
                cnt++;
                vis.add(current);
                if(cnt == n) break;
            }
        }
        return (int)current;
    }

    private boolean isU(int t) {
        while (t % 2 == 0) {
            t = t / 2;
        }
        while (t % 3 == 0) {
            t = t / 3;
        }
        while (t % 5 == 0) {
            t = t / 5;
        }
        return t == 1;
    }
}